package com.cr4y0n.hot100;

import java.net.Inet4Address;
import java.util.HashMap;
import java.util.Map;

/**
 * @author cr4y0n
 * <a href="https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked">最小覆盖子串</a>
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * 示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 * 示例 2：
 * 输入：s = "a", t = "a"
 * 输出："a"
 * 解释：整个字符串 s 是最小覆盖子串。
 * 示例 3:
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 */
public class _76_MinimumWindowSubstring {
    static class Solution {
        public String minWindow(String s, String t) {
            if (s.length() < t.length()) {
                return "";
            }
            HashMap<Character, Integer> tCount = new HashMap<>();
            HashMap<Character, Integer> sCount = new HashMap<>();
            int min = Integer.MAX_VALUE;
            for (char c : t.toCharArray()) {
                tCount.put(c, tCount.getOrDefault(c, 0) + 1);
            }
            int left = 0;
            String res = "";
            //StringBuffer stringBuffer = new StringBuffer();
            for (int right = 0; right < s.length(); right++) {
                sCount.put(s.charAt(right), sCount.getOrDefault(s.charAt(right), 0) + 1);
                while (check(tCount, sCount)) {
                    min = Math.min(min, right - left + 1);
                    if (min == right - left + 1) {
                        //stringBuffer = new StringBuffer();
                        //for (int i = left; i <= right; i++) {
                        //    stringBuffer.append(s.charAt(i));
                        //}
                        res = s.substring(left, right + 1);
                    }
                    sCount.put(s.charAt(left), sCount.get(s.charAt(left)) - 1);
                    left++;
                }
            }
            //return stringBuffer.toString();
            return res;
        }

        public static boolean check(HashMap<Character, Integer> tCount, HashMap<Character, Integer> sCount) {
            for (Map.Entry<Character, Integer> entry : tCount.entrySet()) {
                Character key = entry.getKey();
                Integer value = entry.getValue();
                if (sCount.getOrDefault(key, 0) < value) {
                    return false;
                }
            }
            return true;
        }
    }
}
